It is often required to verify securely the similarity between two signals. The conventional methods use cryptographic hash functions to verify whether two signals are similar. If the hashes of signals x and y are equal, then the signal x is equal to the signal y, assuming that hash collisions occur with negligibly low probability. This comparison of cryptographic hashes is a fundamental building block of most password and key management applications. An essential property of conventional cryptographic hash functions is that the hashes do not preserve the underlying statistical structure of the signals being compared. Specifically, if one signal is a noisy version of the other signal, the cryptographic hashes of the two signals are very different even if the noise is small. Therefore, a cryptographic hash cannot, by itself, be used in noisy environments, e.g., storage or communication channels, to verify inexact matches, because matching based on cryptographic hashes is sensitive to noise.
One method for solving the problem of inexact matches of the signals assumes that one of the signals, e.g., the signal x is transmitted via a noisy channel and received as a corrupted signal y. Then, some error correcting code (ECC) is also transmitted, along with the signal x, to recover an estimated signal {tilde over (x)}. Now, the cryptographic hashes of the signal x and the estimated signal {tilde over (x)} can be compared. If the error correction is successful, then the hashes match exactly, and therefore the signals x and y are, in fact, similar up to some allowable distortion determined by characteristics of the ECC. That method exploits common randomness, and has been widely adopted in fuzzy vault-based schemes for biometric authentication, secure collaboration and image authentication.
However, the above randomness method cannot be utilized if the signals x and y have already been encrypted, which is important in many applications. For instance, a hospital wants medical data to be analyzed and classified by a third party, without revealing the underlying data to the third party. Moreover, the third party might want not to expose the classification method to the hospital. It is often desired to perform the computation in this “double blind” fashion.
This problem is often defined as secure multiparty computation (SMC). Computationally secure methods, such as Oblivious Transfer (OT), Secure Inner Product (SIP) are used as primitives to perform more complicated operations thereby enabling secure multiparty computation. Examples of such methods include blind vision, see U.S. patent application Ser. No. 11,005,293. Those methods perform face detection without revealing the test image supplied by a user or the classification method used by classifier. However, that method requires a large number of key exchanges between the user and the classifier. The overhead, in terms of handshaking and key management, is very large.
Hence, it is often desired to securely verify the similarity between the two signals while minimizing the overhead.